// 
// Copyright (c) 2010 Ben Motmans
// 
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
// THE SOFTWARE.
//
// Author(s):
//    Ben Motmans <ben.motmans@gmail.com>
//

using System;

namespace Anculus.Core
{
	public class Distance
	{
		/// <summary>
		/// Compute Levenshtein distance
		/// Levenshtein Distance Algorithm: C# Implementation
		/// by Lasse Johansen
		/// http://www.merriampark.com/ldcsharp.htm
		/// </summary>
		/// <param name="s">String 1</param>
		/// <param name="t">String 2</param>
		/// <returns>Distance between the two strings.
		/// The larger the number, the bigger the difference.
		/// </returns>
  		public int Levenshtein (string s, string t)
		{
			int n = s.Length;
			int m = t.Length;

			int[,] d = new int[n + 1, m + 1]; // matrix

			int cost;

			// Step 1
			if(n == 0)
				return m;
			
			if(m == 0)
				return n;

			// Step 2
			for(int i = 0; i <= n; d[i, 0] = i++);
			for(int j = 0; j <= m; d[0, j] = j++);
			
			// Step 3
			for(int i = 1; i <= n;i++) {
			
				//Step 4
				for(int j = 1; j <= m;j++) {
			
					// Step 5
					cost = (t.Substring(j - 1, 1) == s.Substring(i - 1, 1) ? 0 : 1);
			
					// Step 6
					d[i, j] = System.Math.Min(System.Math.Min(d[i - 1, j] + 1, d[i, j - 1] + 1),
					d[i - 1, j - 1] + cost);
				}
			}

			// Step 7
			return d[n, m];
		}
	}
}
